import java.util.Arrays;

public class mergeSort {
    public static void sort(int[] nums){
        if(nums==null || nums.length < 2){
            return;
        }
//        大问题
        int[] tmp = new int[nums.length];
        realsort(nums,0,nums.length-1,tmp);

    }
//    1.给子数组排序
    private static void realsort(int[] nums, int left, int right,int[] tmp){
//        终止条件
        if(left == right) return;
//        分成两个子问题
        int mid = (left+right)/2;
        realsort(nums,left,mid,tmp);
        realsort(nums,mid+1,right,tmp);
//        合并两个有序数组[left,mid]和[mid+1,right]
        merge(nums,left,mid,right,tmp);
    }
//    2.合并
    private static void merge(int[] nums,int left,int mid,int right,int[] tmp){
        int n = right-left+1;

        int tmpPos = left;
        int i = left;
        int j = mid +1;

//        将左边和右边的元素按照顺序拷贝到临时数组中
        while (i <= mid && j <= right){
            if(nums[i] <= nums[j]){
                tmp[tmpPos] = nums[i];
                tmpPos++;
                i++;
            }else {
                tmp[tmpPos] = nums[j];
                tmpPos++;
                j++;
            }
        }
//        如果左边还有元素
        while (i <= mid){
            tmp[tmpPos] = nums[i];
            tmpPos++;
            i++;
        }
//        如果右边还有元素
        while (j <= right){
            tmp[tmpPos] = nums[j];
            tmpPos++;
            j++;
        }
//        拷贝
        for(tmpPos = left; tmpPos <= right; tmpPos++){
            nums[left]=tmp[tmpPos];
            left++;
        }
    }

    public static void main(String[] str){
        int[] nums = {22,31,2,1,5,10};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
